(display "\n========================================\n")
(define (encode-symbol symbol tree)
    (cond ((leaf? tree)                                         ; 如果已经到达叶子节点，那么停止积累
            '())
          ((symbol-in-tree? symbol (left-branch tree))          ; 符号在左分支(左子树)，组合起 0
            (cons 0
                  (encode-symbol symbol (left-branch tree))))
          ((symbol-in-tree? symbol (right-branch tree))         ; 符号在右分支(右子树)，组合起 1
            (cons 1
                  (encode-symbol symbol (right-branch tree))))
          (else                                                 ; 给定符号不存在于树，报错
            (error "This symbol not in tree: " symbol))))

(define (symbol-in-tree? given-symbol tree)
    (not
        (false?
            (find (lambda (s)                   ; 使用 find 函数，在树的所有符号中寻找给定符号
                      (eq? s given-symbol))
                  (symbols tree)))))            ; 取出树中的所有符号

(define (make-leaf symbol weight)
    (list 'leaf symbol weight))

(define (leaf? object)
    (eq? (car object) 'leaf))

(define (symbol-leaf x)
    (cadr x))

(define (weight-leaf x)
    (caddr x))

(define (left-branch tree)
    (car tree))

(define (right-branch tree)
    (cadr tree))

(define (make-code-tree left right)
    (list left
          right
          (append (symbols left) (symbols right))
          (+ (weight left) (weight right))))

(define (symbols tree)
    (if (leaf? tree)
        (list (symbol-leaf tree))
        (caddr tree)))

(define (weight tree)
    (if (leaf? tree)
        (weight-leaf tree)
        (cadddr tree)))

(define (encode message tree)
    (if (null? message)
        '()
        (append (encode-symbol (car message) tree)
                (encode (cdr message) tree))))

(define (make-leaf-set pairs)
    (if (null? pairs)
        '()
        (let ((pair (car pairs)))
            (adjoin-set (make-leaf (car pair)
                                   (cadr pair))
                        (make-leaf-set (cdr pairs))))))

(define (adjoin-set x set)
    (cond   ((null? set) (list x))
            ((< (weight x) (weight (car set)))
                (cons x set))
            (else (cons (car set)
                        (adjoin-set x (cdr set))))))

(define (generate-huffman-tree pairs)
    (successive-merge (make-leaf-set pairs)))

(define (successive-merge ordered-set)
    (cond   ((= 0 (length ordered-set)) '())
            ((= 1 (length ordered-set))
                (car ordered-set))
            (else
                (let ((new-sub-tree (make-code-tree (car ordered-set)
                                                    (cadr ordered-set)))
                      (remained-ordered-set (cddr ordered-set)))
                    (successive-merge (adjoin-set new-sub-tree remained-ordered-set))))))

; (define pairs '((NA 16) (YIP 9) (SHA 3) (A 2) (GET 2) (JOB 2) (WAH 1) (BOOM 1)))
(define pairs '((A 1) (NA 16) (BOOM 1) (SHA 3) (GET 2) (YIP 9) (JOB 2) (WAH 1)))
(define tree (generate-huffman-tree pairs))
(define msg-1 '(Get a job))
(define msg-2 '(Sha na na na na na na na na))
(define msg-3 '(Wah yip yip yip yip yip yip yip yip yip))
(define msg-4 '(Sha boom))
(define code-1 (encode msg-1 tree))
(define code-2 (encode msg-2 tree))
(define code-3 (encode msg-3 tree))
(define code-4 (encode msg-4 tree))

(define (show-code code)
    (display code)
    (display "  length: ")
    (display (length code))
    (newline))

(display tree)
(newline)
(show-code code-1)
(show-code code-2)
(show-code code-3)
(show-code code-4)

; Huffman Code: 14 * 2 + 12 * 2 + 23 + 9 = 84
; Fixed Code: 3 * (3 * 2 + 9 * 2 + 10 + 2) = 108

(display "\n========================================\n")
